#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
// int maxScore(char* s)
// {
//     //1.分割两部分--双指针
//     //. 统计左0 和右1 
//     //2.计算 值
//     //3.比较 得结果
//     int i=0; 
//     int x=0;//统计左边 0 个数
    
//     int j=0;
//     int y=0; //统计右边 1 个数
//     int max=0; //记录每一次分割最大值
//     j=strlen(s)-1;

//     int num=1;//作为中间值 i<num. j>=num num++

    
    
//     while(num<=j)
//     {
        
//         //每次置零
//         j=strlen(s)-1;
//         x=0;
//         y=0;
//         int sum=0;
//         // i
//         for(i=0;i<num;i++)
//         {
//             if(s[i]=='0')
//             x++;
//         }
//         // j
//         for(;j>=num;j--)
//         {
//             if(s[j]=='1')
//             y++;
//         }
//         //和
//         sum=x+y;
//         if(sum>=max)
//         max=sum;
//         num++;
//         j=strlen(s)-1;
//     }
//     return max;
    
// }
// int main()
// {
//     char s[]="01001";
//     int ret=maxScore(s);
//     printf("%d\n",ret);
//     return 0;
// }

// char* mergeAlternately(char* word1, char* word2) 
// {
//     //1.找到较长的字符串 和较短的字符串
//     //2.以 min 临界条件 穿插
//     //3.多的追加到后面
//     int max=strlen(word1)>strlen(word2)? strlen (word1):strlen(word2) ;
//     int min=strlen(word1)<strlen(word2)? strlen (word1):strlen(word2) ;

//     char word[200]={0};//新的字符串放在这里
//     int i=0;
//     int j=0;
//     for(i=0;i<min;i++)
//     {
//         if(i%2==0)//下标是偶数 是word1里的元素
        
//             word[i]=word1[j];
        
//         else
//         {
//             word[i]=word2[j];
//             j++;    
//         }
            
//     }
//     if(max==strlen(word1 ))
//     for(;i<max;i++)
//     {
//         word[i]=word1[j];
//         j++;
//     }
//     else
//     for(;i<max;i++)
//     {
//         word[i]=word2[j];
//         j++;
//     }
//     return word;
// }
// int lengthOfLastWord(char* s) {
//     int sz=strlen(s);
//     int  i=0;
//     int count =0;
//     i=sz-1;
//     if(i==0)
//     return 1;
//     else
//     {    while(s[i]==' ')
//     {
//         i--;
//     }
//     //出来后就开始计数
//     while(s[i]!=' '&& i>=0)
//     {
//         count++;
//         i--;
//     }
//     }
//     return count;

// }
// void moveZeroes(int* nums, int numsSize) 
// {   //遍历数组
//     //1.找到0
//     //2.与后一个数交换    
//     int i=0;
//     int sz=numsSize-1;
//     int j=0;
//     for(i=0;i<sz;i++)
//     {
//         for(j=0;j<sz-i;j++)
//         if(nums[j]==0)
//         {
//             //交换
//             int tem=0;
//             tem=nums[j];
//             nums[j]=nums[j+1];
//             nums[j+1]=tem;
//         }
        
//     }
// }
// int main()
// {
//     char s[]="a ";
//     int ret=lengthOfLastWord(s);
//     printf("%d \n",ret);
//     return 0;
// }
//力扣 1491
// int cmp(const void *x,const void *y)
// {
//     int *a1=(int*)x;
//     int *a2=(int*)y;
//     if(*a1>*a2) return 1;
//     if(*a1<*a2) return -1;
//     else
//     return 0;
// }

    
// double average(int* salary, int salarySize) 
// {
//     //1。排序找到最大值最小值 归零
//     //2.数字内容加和球平均
//     qsort(salary,salarySize,sizeof(int),&cmp);
//     double sum=0;
//     for(int i=1;i<salarySize-1;i++)
//     {
//         sum+=salary[i];
//     }
//     return (double)sum/(salarySize-2);
// }
//
// char findTheDifference(char* s, char* t) 
// {
//     //双指针遍历 统计每个元素个数
//     int i=0;
//     int j=0;

//     int s_length=strlen(s);
//     int t_length=strlen(t);

//     int count=0;
//     char ret=0;
//     if(s_length==0)
//     return t[0];

//     for(j=0;j<t_length;j++)
//     {
//         count=0;// 重置
//         for(i=0;i<s_length;i++)
//         {
//             if(s[i]==s[j])
//             {
//                 count++; //如果 >1 说明添加了
//             }
//         }
//          if(count>1 || count==0)
//         {
//             ret=t[j];
//             break;
//         }
//     }
//     return ret; 
// }
// char findTheDifference(char* s, char* t) 
// {
//     //双指针遍历 统计每个元素个数
//     int i=0;
//     int j=0;

//     int x=0;

//     int s_length=strlen(s);
//     int t_length=strlen(t);
    
//     int sum=0;
//     int count=0;

//     char ret=0;
//     if(s_length==0)
//     return t[0];
    
//     while(i<t_length)
//     //一共判断 t 个字符
//     {
//         sum=0;
//         j=i;

//         // t 中第i个字符的个数
//         while(j<t_length)
//         {
//             if(t[j]==t[i])
//             sum++;
//             j++;
//         }

//         //s 中与t[i]== 元素的个数
//         x=0;
//         while(x<s_length)
//         {
//             if(s[x]==t[i])
//             {
//                 count++;
//             }
//             x++;
//         }

//         if(sum!=count)
//         {
//             ret=t[x];
//             break;
//         }
//         i++;
//     }
//     return ret;
// }
// char findTheDifference(char* s, char* t) 
// {
//     int a=0;
//     int b=0;
//     while(*s)
//     a+=(*s++);
//     while(*t)
//     b+=(*t++);
//     return b-a;   
// }
// void fun(long mul,char *str)
// {
//     if(mul>9)
//     {
//     fun(mul/10,str-1);
//     }
//     *str=mul%10+'0'; 
// }
// char str[5]="0";
// char * exch(long mul)
// {
//     *str=mul+'0';
// //     return str;
// }
// void fun(long mul)
// {
//     if(mul>9)
//     fun(mul/10);
//     // printf("%ld\n",mul%10);
//     exch(mul%10);
// }
// long   multiply(char* num1, char* num2) {
//     //1.算术相成
//     //2.转换成字符串
//     double s1=strlen(num1);
//     double s2=strlen(num2);
//     long  x=0;//存num1
//     long  y=0;//存num2
//     long mul=0;
//     int i=0;
//     for(i=0;i<s1;i++)
//     {
//         x=x+(num1[i]-'0')*pow(10.0,s1-1-i);
//     }

//     for(i=0;i<s2;i++)
//     {
//         y=y+(num2[i]-'0')*pow(10.0,s2-1-i);
//     }
//     return mul=x*y;
// }
// void fun(long mul,char *str)
// {
//     if(mul>9)
//     fun(mul/10,str-1);
//     *str=mul%10+'0';
// }
// char* multiply(char* num1, char* num2) {
//     //1.算术相成
//     //2.转换成字符串
//     static char str[400]="0";
//     int s1=strlen(num1);
//     int s2=strlen(num2);
//     long  x=0;//存num1
//     long  y=0;//存num2
//     long mul=0;
//     int count=0;
//     int i=0;
//     for(i=0;i<s1;i++)
//     {
//         x=x+(num1[i]-'0')*pow(10,s1-1-i);
//     }

//     for(i=0;i<s2;i++)
//     {
//         y=y+(num2[i]-'0')*pow(10,s2-1-i);
//     }
//     mul=x*y;//类型是 long
//     //转换成字符串
//     long num=mul;
//     while(num)
//     {
//         num/=10;
//         count++;
//     }
//     fun(mul,&str[count-1]);
//     return str;
// }
#include <ctype.h>
#include <stdbool.h>
// bool isPalindrome(char* s) {
//     int left=0;
//     int right=strlen(s)-1;
    
//     while(left<right)
//     {
//         while(isalpha(s[left])==0)
//         {
//             left++;
//         }
//         while(isalpha(s[right])==0)
//         {
//             right--;
//         }
//         if(isalpha(s[left]) && isalpha(s[right]) && tolower(s[left]
//         )!=tolower(s[right]))
//         break;
//         left++;
//         right--;
//     }

//     if(left>=right)
//     return true;
//     else
//     return false;
// }
// bool judge(char str)
// {
//     str=tolower(str);
//     if(str=='a' || str=='e' || str=='o' || str=='i' ||str=='u')
//     return true;
//     else
//     return false;
// }
// char* reverseVowels(char* s) {
//     //1双指针左右开弓
//     //2.判断元音字母
//     //3.交换 tem
//     int right=strlen(s)-1;
//     int left=0;
//     bool l;
//     bool r;
//     while(left<right)
//     {
//         l=judge(s[left]);
//         r=judge(s[right]);

//         //两个都是元音

//         if(l==r && l==true)
//         {
//             char tem=0;
//             tem=s[right];
//             s[right]=s[left];
//             s[left]=tem;
//             left++;
//             right--;
//         }
//         else if(l==false)
//         {
//             left++;
//         }
//         else if(r==false)
//         {
//             right--;
//         }
//         else if(r==l && l==false)
//         {
//             left++;
//             right--;
//         }
//     }
//     return s;
// }
// bool canConstruct(char* ransomNote, char* magazine) {
//     //判断 r 是不是 m 的子串
//     //双指针分别遍历两个字符串
//     //r-->ran. m-->ma m每次归零
//     int r=0;
//     int m=0;

//     int sz1=strlen(ransomNote);
//     int sz2=strlen(magazine);

//     //字符长度都小于 那就返回false
//     if(sz2<sz1)
//     return false;
//     int judge=0;
//     //找到
//     for(r=0;r<sz1;r++)
//     {
//         judge=0;
//         //遍历 m 字符串
//         for(m=0;m<sz2;m++)
//         {
//              //r+1, ma 里的变成‘0’
//             if(ransomNote[r]==magazine[m])
//             {
//                 judge=1;
//                 magazine[m]='0';
//                 break;
//             }
//             else
//             {
//                 judge=0;
//             }
//         }
//         //m字符串遍历完出来
//         if(judge==0)// 没找到 直接结束
//         return false;
    
//     }
//     return true;

// }
// int * bubble_sort(int *nums,int size)
// {
//     int i=0;
//     int j=0;
//     int tmp=0;
//     for(i=0;i<size-1;i++)
//     {
        
//         for(j=0;j<size-i-1;j++)
//         {
//             if(nums[j]>nums[j+1])
//             {
                
//                 tmp=nums[j+1];
//                 nums[j+1]=nums[j];
//                 nums[j]=tmp;
                
//             }
//         }
//         // if(count==0)
//         // break;
//     }
//     return nums;
// // }
// int findKthLargest(int* nums, int numsSize, int k) {
//     //1.冒泡升序
//     int i=0;
//     int j=0;
//     int tmp=0;
//     for(i=0;i<numsSize-1;i++)
//     {
//         for(j=0;j<numsSize-1-i;j++)
//         {
//             if(nums[j]>nums[j+1])
//             {
//                 tmp=nums[j+1];
//                 nums[j+1]=nums[j];
//                 nums[j]=tmp;
//             }
//         }
//     }
    
//     //2.循环找的第 k 大的数字
//     int count=0;
//     int ret=0;
//     for(j=numsSize-1;j>0;j--)
//     {
//         if(nums[j]>=nums[j-1])
//         {
//             count++;
//         }
//         if(count==k)
//         {
//             ret=nums[j];
//             break;
//         }
//     }
//     if(j==0)
//     ret=nums[0];
//     return ret;
// }
// int main()
// {
//     printf("hello bit\n");
//     return 0;
// }
// #include <stdio.h>
// //选择排序

// int scanformin(int arr[] ,int i,int n)
// {

// }
// void SelectionSort(int arr[],int n)
// {
//     int i=0;
//     int tmp=0;
//     for(i=0;i<n;i++)
//     {
//         int minposition=scanformin(arr,i,n-1);
//         //swap(list[i],minposition);
//     }
// }
// int main()
// {
//     int arr[8]={6,7,0,3,2,5,8,1};
//     SelectionSort(arr,8);
//     return 0;
// }
#include <stdio.h>
// int main()
// {
//     int nums[]={1,1,1,1};
//     int numsSize=sizeof(nums)/sizeof(nums[0]);
//     int count=0;
//     int begin=0;
//     int end=numsSize-1;
//     for(begin=0;begin<end;begin++)
//     {
//         for(end=numsSize-1;end>begin;end--)
//         {
//             if(nums[end]==nums[begin])
//             {
//                 count++;
//             }
//         }
//         //重置
//         end=numsSize-1;
//     }
//     printf("%d\n",count);
//     return 0;
// }
#include <math.h>
int ak(int a,int b)
{
    return abs(a-b);
}
int countGoodTriplets(int* arr, int arrSize, int a, int b, int c) {
    int i=0;
    int count=0;
    for(i=0;i<arrSize;i++)
    {
        for(int j=i+1;j<arrSize;j++)
        {
            for(int k=j+1;k<arrSize;k++)
            {
                if((ak(arr[i],arr[j])<=a) &&(ak(arr[j],arr[k])<=b)&&(ak(arr[i],arr[k])<=c))
                count++;
            }
        }
    }
    return count;
}
bool isPowerOfTwo(int n) {
    //1 , 2,4,8,16
    if(n==1)
    return true;
    while(n>9)
    {
        if(n%2!=0)
        return false;
        else
        n/=2;

    }
    if(n==2 || n==4 ||n==8)
    {
        return true;
    }
    else
    return false;
}
bool judge(char a)
{
    if(a=='a'||a=='e'||a=='i'||a=='o'|| a=='u')
    return true;
    else
    return false;
}
int vowelStrings(char** words, int wordsSize, int left, int right) {
    int len=0;
    int i=0;
    int count=0;
    for(;left<=right;left++)
    {
        len=strlen(words[left]);
        if(judge(words[left][i]) && judge(words[left][len-1]))
        {
            count++;
        }
    }
    return count;
}
int peakIndexInMountainArray(int* arr, int arrSize) {
    //返回下标
    int i=0;
    int maxi=0;
    for(i=0;i<arrSize;i++)
    {
        if(arr[i]>arr[maxi])
        {
            maxi=i;
        }
    }
    return maxi;
}
int missingNumber(int* nums, int numsSize) {
    //消失的数字 数学加和求差值更快
    int i=0;
    int j=0;
    for(i=0;i<numsSize-1;i++)
    {
        for(j=0;j<numsSize-i-1;j++)
        {
            if(nums[j]>nums[j+1])
            {
                int tem=0;
                tem=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=tem;
            }
        }
    }
    int ret=0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]!=i)
        {
           ret=i;
           break;
        }
    }
    return ret;

}
bool isThree(int n) {
    int k=0;
    int m=0;
    int count=0;
    for(k=1;k<=n;k++)
    {
        for(m=1;m<=n;m++)
        {
            if(n==k*m)
            count++;
        }
    }
    if(count==3)
    return true;
    else
    return false;
}
// int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
//     for (int i = 0; ; i++) { // 枚举 i
//         for (int j = i + 1; j < numsSize; j++) { // 枚举 i 右边的 j
//             if (nums[i] + nums[j] == target) { // 满足要求
//                 int* ans = malloc(2 * sizeof(int)); // 分配返回结果的内存空间
//                 *returnSize = 2; // ans 的长度
//                 ans[0] = i; // 存储第一个数的下标
//                 ans[1] = j; // 存储第二个数的下标
//                 return ans; // 返回结果数组的指针
//             }
//         }
//     }
//     // 题目保证有解，循环中一定会 return
//     // 所以这里无需 return，毕竟代码不会执行到这里
// }

int searchInsert(int* nums, int numsSize, int target) {
    int begin=0;
    int ret=0;
    int count=0;
    for(begin=0;begin<numsSize;begin++)
    {
        if(target>nums[begin])
        {
            ret=begin;
            count++;
        }
        else
        break;
    }
    if(count==0)
    return ret;
    else
    return ret+1;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize) {
    
    int right=digitsSize-1;
    *returnSize=digitsSize;

    int judge=digits[right]+1;
    if(judge==10)
    //进位
    {//9
                

        while(judge==10)
        {
            if(right>0)    
            {
                digits[right]=0;
                right-=1;   
                //更新judge    
                judge=digits[right]+1; 
            }
            //最高位进位 right==0
            else if(right==0 && judge==10)
            {
                // 多开辟一个整形的空间
                break;
            }
        }
        //跳出循环两种情况
        if(judge==10)
       {
            *returnSize+=1;
            digits[right]=0;
       }
        else
         digits[right]=judge;

    }
    else
    //不用进位直接输出
        {
             digits[right]=judge;
        }
           

    //输出
    int *arr=(int*)malloc(*returnSize*sizeof(int));
    
    if(digits[0]==0)//说明最高位进位了
    {
        arr[0]=1;
        int i=0;
        for(i=1;i<*returnSize;i++)
        {
            arr[i]=digits[i-1];
        }
    }
    else
    {
        int i=0;
        for(i=0;i<*returnSize;i++)
        {
            arr[i]=digits[i];
        }
    }
    return arr;
}
int main()
{
    int nums[]={3,0,1};

    int ret=missingNumber(nums,3);
    printf("%d\n",ret);
    return 0;
}